import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

public class TT {
    public static void main(String[] args) throws InterruptedException {

        int[] arr = {5, 1, 7, 3, 6, 9, 4};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }

    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        //从左边选取一个位的数据作为中值（随机选取，记住位置）
        int piovt = arr[left];
        //第一次分位： 两个循环交替切换，如：从右边开始找，找比piovt小的，找到后移动到刚刚记住的位置，移动到空缺的位置，
        while (left < right) {
            while (right>left && arr[right] >= piovt) right--;
            arr[left] = arr[right];
            while (left<right && arr[left] <= piovt)  left++;
            arr[right] = arr[left];
        }
        arr[left]=piovt;
        //左边递归分位
        quickSort(arr, leftIndex, left - 1);
        //右边递归分位
        quickSort(arr, right + 1, rightIndex);
    }

}
